public class Grafo 
{
	private No []no;
	private int k,n,m,l,c,p;
	public void No()
	{
		no=new No[10];
		k=0;
	}
	public void addNo(No d)
	{
		no[k]=d;
		k++;
	}
	public No[] getNo()
	{
		return no;
	}
	public void criarAresta(int i, int j)
	{
		no[i].ligar(no[j]);
		no[j].ligar(no[i]);
	}
	public Grafo menorCaminho(No a,No b)
	{
		for(k=0;k<10;k++)
		{
			no[k].setDistancia(1000);
			no[k].setCor("branco");
		}
		a.setDistancia(0);
		a.setCor("cinza");
		no[0]=a;
		no[9]=b;
		c=1;
		while(c>0)
		{
			for(k=0;k<10;k++)
			{
				if(no[k].getCor()=="cinza")
				{
					n=no[k].getDistancia();
					l=k;
					for(m=k+1;m<10;m++)
					{
						if(no[m].getCor()=="cinza"&&no[m].getDistancia()<n)
						{
							n=no[m].getDistancia();
							l=m;
						}
					}
				}
			}
			No z=no[l];
			z.setCor("preto");
			c--;
			no[l]=z;
			Aresta v[]=no[l].getAresta();
			for(p=0;v[p]!=null;p++)
			{
				if(v[p].getDestino().getCor()=="branco"||v[p].getDestino().getCor()=="cinza")
				{
					No w=v[p].getDestino();
					if(w.getDistancia()>z.getDistancia()+v[p].getPeso())
					{
						w.setDistancia(z.getDistancia()+v[p].getPeso());
						w.setPai(z);
						if(w.getCor()=="branco")
						{
							w.setCor("cinza");
							c++;
						}
					}
					for(k=0;k<10;k++)
					{
						if(no[k].getDescricao()==w.getDescricao())
						{
							no[k]=w;
						}
					}
				}
			}
		}
		Grafo R=new Grafo();
		R.addNo(b);
		No x=b;
		if(b==a)
		{
			R.addNo(b);
		}
		else
		{
			if(a==b.getPai())
			{
				R.addNo(a);
			}
			else
			{
				while(x.getPai()!=a)
				{
					x=x.getPai();
					R.addNo(x);
				}
			}
		}
		No []g =R.getNo();
		for(l=0;g[l+1]!=null;l++)
		{
			R.criarAresta(l,l+1);
		}
		return R;
	}
}
